package com.zjj.algorithm.learning.leetcode.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 02.01. 移除重复节点 简单题
 * <p>
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 * <p>
 * 示例1:
 * <p>
 * 输入：[1, 2, 3, 3, 2, 1]
 * 输出：[1, 2, 3]
 * 示例2:
 * <p>
 * 输入：[1, 1, 1, 1, 2]
 * 输出：[1, 2]
 * 提示：
 * <p>
 * 链表长度在[0, 20000]范围内。
 * 链表元素在[0, 20000]范围内。
 * 进阶：
 * <p>
 * 如果不得使用临时缓冲区，该怎么解决？
 *
 * @author zjj_admin
 * @date 2022/12/14 17:44
 */
public class RemoveDuplicateNodeLcci {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1, null);
        ListNode node2 = new ListNode(2, node1);
        ListNode node3 = new ListNode(3, node2);
        ListNode node4 = new ListNode(3, node3);
        ListNode node5 = new ListNode(2, node4);
        ListNode node6 = new ListNode(1, node5);
        removeDuplicateNodes(node6);
    }

    /**
     * 时间
     * 4 ms
     * 击败
     * 94.2%
     * 内存
     * 42.7 MB
     * 击败
     * 65.8%
     *
     * @param head
     * @return
     */
    public static ListNode removeDuplicateNodes(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = new ListNode();
        pre.next = head;
        ListNode dump = pre;
        Set<Integer> set = new HashSet<>();
        while (pre.next != null) {
            if (!set.contains(pre.next.val)) {
                set.add(pre.next.val);

                pre = pre.next;
            } else {
                pre.next = pre.next.next;
            }
        }
        return dump.next;
    }


}
